Definition

A t-out-of-n threshold secret-sharing scheme (TSSS) consists of algorithms

  • 𝖲𝗁𝖺𝗋𝖾\mathsf{Share}: randomized algorithm that takes a message m∈ℳm \in \mathcal{M} as input, and outputs a sequence 𝐬=(s1,...,sn)\mathbf{s} = (s_1,...,s_n) of shares
  • 𝖱𝖾𝖼𝗈𝗇𝗌𝗍𝗋𝗎𝖼𝗍\mathsf{Reconstruct}: deterministic algorithm that takes a collection of tt or more shares, and outputs a message

Consider ℳ\mathcal{M} the message space of the scheme, and tt its threshold, scheme Σ\Sigma

correctness

A TSSS satisfies correctness if for all authorized sets U⊆{1,...,n}U \subseteq \{1,...,n\} (i.e. |U|≥t|U| \geq t and for all 𝐬←𝖲𝗁𝖺𝗋𝖾(m)\mathbf{s} \gets \mathsf{Share}(m), 𝖱𝖾𝖼𝗈𝗇𝗌𝗍𝗋𝗎𝖼𝗍({si|i∈U})=m\mathsf{Reconstruct}(\{s_i \vert i \in U\}) = m

security

intuition: if you know unauthorized number of shares, then you learn no information about the choice of secret message

formally:
Let Σ\Sigma be a TSSS, then Σ\Sigma is said to be secure if ℒ𝗍𝗌𝗌𝗌-𝖫Σ=ℒ𝗍𝗌𝗌𝗌-𝖱Σ\mathcal{L}_{\textsf{tsss-L}}^\Sigma=\mathcal{L}_{\textsf{tsss-R}}^\Sigma
where for ℒ𝗍𝗌𝗌𝗌-𝖫Σ\mathcal{L}_{\textsf{tsss-L}}^\Sigma, SHARE(mL,mR∈Σ.ℳ,U)\text{SHARE}(m_L, m_R \in \Sigma.\mathcal{M}, U) returns err if |U|≥Σ.t|U| \geq \Sigma.t, else, 𝐬←Σ.𝖲𝗁𝖺𝗋𝖾(mL)\mathbf{s} \gets \Sigma.\mathsf{Share}(m_L), and {si|i∈U}\{s_i | i \in U\} is returned. ℒ𝗍𝗌𝗌𝗌-𝖱Σ\mathcal{L}_{\textsf{tsss-R}}^\Sigma is similarly described, but for mRm_R. U⊆{1,...,Σ.n}U \subseteq \{1,...,\Sigma.n\}

Notes

  • the one-time pad may be considered as the simplest secret-sharing scheme, 2-out-of-2, where
    • Share(m): s1←{0,1}ℓs_1 \gets \{0,1\}^\ell, s2:=s1⊕︎ms_2 := s_1 \oplus m
    • Reconstruct(s1,s2s_1,s_2): return s1⊕︎s2s_1 \oplus s_2
  • furthermore, OTP satisfies security as a 2-out-of-2 TSSS

References

  1. https://joyofcryptography.com/pdf/chap3.pdf